描述

传送门：自杀游戏

Alice和Bob产生了不可调节的矛盾，于是他们相约一起玩一个自杀游戏，输的人就会从这个世界上消失。

游戏开始时，Alice手上拿着一个定时炸弹，炸弹有个倒计时t。炸弹在t=0时刻会爆炸，此时手上拿着炸弹的人会从这个世界上消失。为了增加游戏乐趣，他们约定每个人拿到炸弹后可以选择将炸弹的时间调快d秒(d ∈ [a,b])，或者不调。每次交换炸弹会消耗1秒（假设调节炸弹时间不需要消耗时间）。

问题来了，如果双方都足够聪明，谁会活下去呢？

输入描述

第一行有三个整数t,a,b，分别表示炸弹初始时刻的倒计时，可调节时间的范围。(0 ≤ t ≤ 10^5,1 ≤ a ≤ b ≤ 10)

输出描述

若Alice存活则输出”Alice”，若Bob存活则输出”Bob”。

示例

输入

6 3 4

输出

Alice

Hint

Alice只需要将炸弹调快3秒后再给Bob，Bob就会拿到一个2秒后爆炸的炸弹。

题解

题目大意

友好的中文题面

思路

所以我们可以假定一个状态state[t]表示炸弹时间为t的存活状态,

state[t]==1表示Alice在t时刻存活,Bob死亡,

state[t]==0表示在t时刻Alice死亡, Bob存活.

然后每次可以调控[a,b]的时间,同时传递炸弹需要1秒,

所以,我们的状态可以这样转移:
当state[t-(b+1)]...state[t-(a+1)]存在一个state[x]==0时 state[t] = 1 

或者 当 state[t-1]==0时 state[t] = 1
可以理解为: 如果时间为炸弹[t-1]或者[t-(b+1)]~[t-(a+1)]的游戏的结果都是最优解了,而现在炸弹的时间增加了,所以如果在过去的一段区间出现Alice死亡的结局,那么现在就可以翻转这个结局了.

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+500;
bool living[maxn]; // living[t]==true表示t时刻Alice活,Bob死 

int main() {
    int i, j, t, a, b;
    scanf("%d%d%d", &t, &a, &b);
    for (i=1; i<=t; ++i) {
        if (!living[i-1]) living[i] = true; // 表明上一次游戏的最优解Alice死,Bob活,状态转移,当前游戏的Alice活,Bod死 
        for (j=i-b-1; j<=i-a-1; ++j) {      // 因为传递炸弹要用1秒 所以还要减一 
            if (j>=0 && !living[j]) {       // 表明上一次游戏的最优解有Alice死,Bob活,状态转移,当前游戏的Alice活,Bod死 
                living[i] = true;
                break;
            }
        }
    }
    printf("%s\n", living[t] ? "Alice" : "Bob" );
    return 0;
}